/**
 * 给定一个二叉树，找出其最小深度。
 * 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
 * 
 * 
 * 返回它的最小深度 2
 *  3
   / \
  9  20
    /  \
   15   7

 */


// bfs
var minDepth = function (root) {
    if (root === null) return 0
    if (!root.left && !root.right) return 1
    const queue = [root]
    let depth = 0
    while (queue.length !== 0) {
        let size = queue.length
        let i = 0
        for (; i < size; i++) {
            let cur = queue.shift()
            if(!cur.left && !cur.right) break
            if(cur.left) {queue.push(cur.left)}
            if(cur.right) {queue.push(cur.right)}
        }
        if(i === size) {
            depth++
        } else return depth+1
    }
};



// dfs
var minDepth = function(root) {
    if(root == null) {
        return 0;
    }
    if(root.left == null && root.right == null) {
        return 1;
    }
    let ans = Number.MAX_SAFE_INTEGER;
    if(root.left != null) {
        ans = Math.min(minDepth(root.left), ans);
    }
    if(root.right != null) {
        ans = Math.min(minDepth(root.right), ans);
    }
    return ans + 1;
};
